/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    var preN *TreeNode
    cur := root
    for cur != nil {
        if cur.Val == key {
            break
        }
        preN = cur
        if key < cur.Val {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    if preN == nil {
        return deleteOneNode(cur)
    }
    if preN.Left != nil && preN.Left.Val == key {
        preN.Left = deleteOneNode(cur)
    }
    if preN.Right != nil && preN.Right.Val == key {
        preN.Right = deleteOneNode(cur)
    }
    return root
}

// 将节点的左孩子树移动到右孩子树的最左边
// 返回右子树根节点
func deleteOneNode (node *TreeNode) *TreeNode {
    if node == nil {
        return nil
    }
    if node.Right == nil {
        return node.Left
    }
    cur := node.Right
    for cur.Left != nil {
        cur = cur.Left
    }
    cur.Left = node.Left
    return node.Right
}